The present invention relates generally to nonvolatile memories and to methods of storing data in such memories. In particular the present invention relates to methods of encoding data for storage in nonvolatile memories and to memory systems that use such encoding. All patents, patent applications and other documents cited in the present application are hereby incorporated by reference in their entirety, for all purposes.
There are many commercially successful non-volatile memory products being used today, particularly in the form of small form factor cards, which employ an array of flash EEPROM (Electrically Erasable and Programmable Read Only Memory) cells formed on one or more integrated circuit chips. A memory controller, usually but not necessarily on a separate integrated circuit chip, interfaces with a host to which the card is removably connected and controls operation of the memory array within the card. Such a controller typically includes a microprocessor, some non-volatile read-only-memory (ROM), a volatile random-access-memory (RAM) and one or more special circuits such as one that calculates an error-correction-code (ECC) from data as they pass through the controller during the programming and reading of data. Some of the commercially available cards are CompactFlash™ (CF) cards, MultiMedia cards (MMC), Secure Digital (SD) cards, Smart Media cards, personnel tags (P-Tag) and Memory Stick cards. Other removable flash memory systems include those having USB connections, such as the “Cruzer®” line of products from SanDisk. Hosts include personal computers, notebook computers, personal digital assistants (PDAs), various data communication devices, digital cameras, cellular telephones, portable audio players, automobile sound systems, and similar types of equipment. Besides the memory card implementation, this type of memory system can alternatively be embedded into various types of host systems.
Two general memory cell array architectures have found commercial application, NOR and NAND. In a typical NOR array, memory cells are connected between adjacent bit line source and drain diffusions that extend in a column direction with control gates connected to word lines extending along rows of cells. A memory cell includes at least one storage element positioned over at least a portion of the cell channel region between the source and drain. A programmed level of charge on the storage elements thus controls an operating characteristic of the cells, which can then be read by applying appropriate voltages to the addressed memory cells. Examples of such cells, their uses in memory systems and methods of manufacturing them are given in U.S. Pat. Nos. 5,070,032, 5,095,344, 5,313,421, 5,315,541, 5,343,063, 5,661,053 and 6,222,762.
The NAND array utilizes series strings of more than two memory cells, such as 16 or 32, connected along with one or more select transistors between individual bit lines and a reference potential to form columns of cells. Word lines extend across cells within a large number of these columns. An individual cell within a column is read and verified during programming by causing the remaining cells in the string to be turned on hard so that the current flowing through a string is dependent upon the level of charge stored in the addressed cell. Examples of NAND architecture arrays and their operation as part of a memory system are found in U.S. Pat. Nos. 5,570,315, 5,774,397, 6,046,935, and 6,522,580.
The charge storage elements of current flash EEPROM arrays, as discussed in the foregoing referenced patents, are most commonly electrically conductive floating gates, typically formed from conductively doped polysilicon material. An alternate type of memory cell useful in flash EEPROM systems utilizes a non-conductive dielectric material in place of the conductive floating gate to store charge in a non-volatile manner. A triple layer dielectric formed of silicon oxide, silicon nitride and silicon oxide (ONO) is sandwiched between a conductive control gate and a surface of a semi-conductive substrate above the memory cell channel. The cell is programmed by injecting electrons from the cell channel into the nitride, where they are trapped and stored in a limited region, and erased by injecting hot holes into the nitride. Several specific cell structures and arrays employing dielectric storage elements and are described in U.S. Pat. No. 6,925,007 of Harari et al.
As in most integrated circuit applications, the pressure to shrink the silicon substrate area required to implement some integrated circuit function also exists with flash EEPROM memory cell arrays. It is continually desired to increase the amount of digital data that can be stored in a given area of a silicon substrate, in order to increase the storage capacity of a given size memory card and other types of packages, or to both increase capacity and decrease size. One way to increase the storage density of data is to store more than one bit of data per memory cell and/or per storage unit or element. This is accomplished by dividing a window of a storage element charge level voltage range into more than two states. The use of four such states allows each cell to store two bits of data, eight states stores three bits of data per storage element, and so on. Multiple state flash EEPROM structures using floating gates and their operation are described in U.S. Pat. Nos. 5,043,940 and 5,172,338, and for structures using dielectric floating gates in aforementioned U.S. Pat. No. 6,925,007. Selected portions of a multi-state memory cell array may also be operated in two states (binary) for various reasons, in a manner described in U.S. Pat. Nos. 5,930,167 and 6,456,528.
Memory cells of a typical flash EEPROM array are divided into discrete blocks of cells that are erased together. That is, the block is the erase unit, a minimum number of cells that are simultaneously erasable. Each block typically stores one or more pages of data, the page being the minimum unit of programming and reading, although more than one page may be programmed or read in parallel in different sub-arrays or planes. Each page typically stores one or more sectors of data, the size of the sector being defined by the host system. An example sector includes 512 bytes of user data, following a standard established with magnetic disk drives, plus some number of bytes of overhead information about the user data and/or the block in which they are stored. Such memories are typically configured with 16, 32 or more pages within each block, and each page stores one or just a few host sectors of data.
Individual flash EEPROM cells store an amount of charge in a charge storage element or unit that is representative of one or more bits of data. The charge level of a storage element controls the threshold voltage (commonly referenced as VT) of its memory cell, which is used as a basis of reading the storage state of the cell. A threshold voltage window is commonly divided into a number of ranges, one for each of the two or more storage states of the memory cell. These ranges are separated by guardbands that include a nominal sensing level that allows determining the storage states of the individual cells. These storage levels may shift as a result of charge disturbing programming, reading or erasing operations performed in neighboring or other related memory cells, pages or blocks. This shift can cause a cell Vt to escape the voltage window into which it was intended during programming. During sensing, this shift may affect the value of the data read. This value appears externally as a change in the data read from the data programmed. Error correcting codes (ECCs) are therefore typically calculated by the controller and stored along with the input data being programmed and used during reading to verify the data and perform some level of data correction if necessary. After such corrections, shifting charge levels can be restored back to the centers of their state ranges from time-to-time, before disturbing operations cause them to shift completely out of their defined ranges and thus cause erroneous data to be read. This process, termed data refresh or scrub, is described in U.S. Pat. Nos. 5,532,962 and 5,909,449.
FIG. 1A shows the threshold voltages (VT) of memory cells A-D in a nonvolatile memory array using binary storage. Two ranges of threshold voltage correspond to two logical states, logic 1 and logic 0. Thus, cells B and D store a logical “1” while cells A and C store a logical “0.” However, threshold voltages of individual cells with a particular logical state may differ because of physical differences in the cells, differences in programming, disturbances that affect the programmed threshold voltages, or for other reasons. FIG. 1B shows the distributions of threshold voltages of cells programmed to logic 1 and logic 0 states. The vertical axis of FIG. 1B represents the number of cells (N) at a particular threshold voltage. Each logical state shows a distribution of threshold voltage values about a mean value. No overlap is shown between the distribution for logic 1 and the distribution for logic 0. While some finite probability may exist for a threshold voltage of a cell programmed to a particular logical state to be in the threshold voltage range associated with the other state, for most memories this is an extremely low probability and so relatively weak ECC may be used for binary programming schemes. For example, a single-bit correcting Hamming code has commonly been used in flash memory systems employing binary NAND flash memory.
FIG. 2A shows the threshold voltages of memory cells E-H in another memory system using Multi-Level Cell (MLC) storage. Four ranges of threshold voltage correspond to four logical states in this example. These four logical states represent two bits of data. Thus, cells E and G store a logical “10” cell F stores “00” and cell H stores “01.” As with the binary storage example of FIGS. 1A and 1B, threshold voltages of cells in a particular logical state (such as cells E and G) are not all identical. FIG. 2B shows the distributions of threshold voltages for cells in logical states 11, 10, 01, 00.
FIG. 2B shows separation between distributions so that the threshold voltage of a cell clearly indicates one logical state.
FIG. 2C shows another distribution of threshold voltages for cells in logical states 11, 10, 01, 00. Unlike the distributions of FIG. 2B, some overlap occurs between threshold voltage distributions of different logical states. This means that a memory cell that is programmed to a particular logical state may later be read as having a different logical state. For example, a cell programmed with “01” may later be read as “10.” This problem generally becomes worse as the number of logical states stored in a cell is increased. One way to deal with this problem is to use Error Correcting Codes (ECC).
FIG. 3 shows a sector of data 300 that is stored in a nonvolatile memory array. Sector 300 includes input data 302 (host data, firmware or system data) and overhead data 304a, 304b. Overhead data 304a, 304b may be in one or more fields that are not necessarily contiguous and are associated with one or more data fields (such as firmware, control data, or other system information). The overhead data typically contain sector mapping information, control flags and ECC data. Here, overhead data 304a, 304b include a header 304a and ECC data 304b. The ECC data 304b covers the input data 302 itself, and optionally some or all of the overhead data 304a, 304b. In one example, 512 bytes of input data are provided in a sector with 16 bytes of overhead data. Of the 16 bytes of overhead data, 9 bytes of ECC data are provided in one example. The ECC data are generated from the input data when the input data are stored. Subsequently, when the stored data are read, ECC data are read as part of the operation and are used to identify errors in the input data. If the number of bits in error does not exceed the correction capability of the ECC, ECC can be used to correct the errors. The number of erroneous bits, which represents a difference between the data programmed and the data read, is referred to as the Hamming distance. If the Hamming distance exceeds the correction capability of the ECC but not the detection capability of the ECC, ECC can be used to detect the errors but not to correct them. If the Hamming distance is even larger such that it exceeds the detection capability of the ECC, the use of ECC may incorrectly identify and attempt to correct inappropriate errors in the data errors or may give a false indication that the data is correct. These occurrences are referred to as data miscorrection and data misdetection, respectively. All conventional ECC has such limitations in its ability to detect and correct errors.